package com.xuexi.mashibing;

import com.xuexi.yilai.ListNode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.stream.Collectors;

public class LeetCode {

    public static void main(String[] args) {
//        ListNode ln1_0 = new ListNode(2);
//        ListNode ln1_1 = new ListNode(4);
//        ListNode ln1_2 = new ListNode(3);
//        ListNode ln1_3 = new ListNode(44);
//        ListNode ln1_4 = new ListNode(13);
//        ListNode ln1_5 = new ListNode(8);
//        ln1_0.next = ln1_1;
//        ln1_1.next = ln1_2;
//        ln1_2.next = ln1_3;
//        ln1_3.next = ln1_4;
//        ln1_4.next = ln1_5;
//
//        ListNode ln2_0 = new ListNode(5);
//        ListNode ln2_1 = new ListNode(6);
//        ListNode ln2_2 = new ListNode(4);
//        ln2_0.next = ln2_1;
//        ln2_1.next = ln2_2;
//
//        addTwoNumbers(ln1_0, ln2_0);

        //System.out.println(fib(8));

        System.out.println(convert("abcdefghijk", 4));

//        double x = Math.pow(2, 31) - 1;
//        System.out.println(x);
//        System.out.println((int) x);
//        System.out.println(reverse(1534236469));
//        //int a = 96463243351;
//        System.out.println();


//        System.out.println(lengthOfLongestSubstring("abcdefghijk"));

//        System.out.println(subStrLength(" "));
//        double x = Math.pow(2, 31) - 1;
//        System.out.println(x);
//        System.out.println((int) x);
//        System.out.println(reverse(1534236469));
//        //int a = 96463243351;
//        System.out.println();

//        ListNode listNode = sortList(ln1_0);
//        System.out.println(listNode);
//
//        ListNode listNode1 = sortList(ln1_0, null);
//        System.out.println(listNode1);
//
//        System.out.println(isMatch("bcd", ".bc."));
    }

    /**
     * 两数之和
     * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
     *
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return null;
    }


    /**
     * 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
     * <p>
     * 请你将两个数相加，并以相同形式返回一个表示和的链表。
     * <p>
     * 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
     * 每个链表中的节点数在范围 [1, 100] 内
     * 0 <= Node.val <= 9
     * 题目数据保证列表表示的数字不含前导零
     *
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode sum = new ListNode();
        ListNode temp = l1;
        ListNode tempSum = sum;
        while (null != temp.next) {
            if (null == tempSum.next) {
                tempSum.next = new ListNode();
            }
            tempSum.val += temp.val;
            tempSum = tempSum.next;
            temp = temp.next;
        }
        tempSum.val = temp.val;
        temp = l2;
        tempSum = sum;
        while (null != temp.next) {
            if (null == tempSum.next) {
                tempSum.next = new ListNode();
            }
            tempSum.val += temp.val;
            tempSum = tempSum.next;
            temp = temp.next;
        }
        tempSum.val += temp.val;
        tempSum = sum;
        while (null != tempSum.next) {
            if (tempSum.val > 9) {
                int x = tempSum.val;
                tempSum.val = x % 10;
                tempSum.next.val += 1;
            }
            tempSum = tempSum.next;
        }
        if (tempSum.val > 9) {
            int x = tempSum.val;
            tempSum.val = x % 10;
            tempSum.next = new ListNode();
            tempSum.next.val += 1;
        }
        return sum;
    }

    /**
     * 子串‌是字符串中任意个连续的字符组成的子序列
     * <p>
     * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串的长度。
     *
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring(String s) {
        char[] chars = s.toCharArray();
        Map<Character, Integer> subChars = new HashMap<Character, Integer>(chars.length);
        int maxSize = 0;
        int repeatIndex = -1;
        int i = 0;
        while (i < chars.length) {
            for (int j = i; j < chars.length; j++) {
                char c = chars[j];
                if (subChars.containsKey(c)) {
                    repeatIndex = subChars.get(c);
                    break;
                }
                subChars.put(c, j);
            }
            if (repeatIndex != -1) {
                // 找到重复元素，从第一个重复元素的下一个下标开始遍历
                i = repeatIndex + 1;
                repeatIndex = -1;
            } else {
                i++;
            }
            maxSize = Math.max(maxSize, subChars.size());
            subChars.clear();
//            float middleSize = chars.length / 2f;
//            if (maxSize >= middleSize && i >= middleSize) {
//                // 最大子串长度超过一半了，可以不用继续遍历了
//                break;
//            }
        }
        return maxSize;
    }

    public static int subStrLength(String s) {
        if (s == null) {
            return 0;
        }
        char[] chars = s.toCharArray();
        Map<Character, Integer> charIndex = new HashMap<>();
        int maxLength = 0, tempLength = 0;
        for (int i = 0; i < chars.length; i++) {
            char c = chars[i];
            if (charIndex.containsKey(c)) {
                i = charIndex.get(c);
                charIndex.clear();
                maxLength = Math.max(maxLength, tempLength);
                tempLength = 0;
            } else {
                charIndex.put(c, i);
                tempLength++;
            }
        }
        return Math.max(maxLength, tempLength);
    }


    /**
     * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
     * <p>
     * 算法的时间复杂度应该为 O(log (m+n)) 。
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        double d = 0.0;
        int[] a = new int[nums1.length + nums2.length];
        System.arraycopy(nums1, 0, a, 0, nums1.length);
        System.arraycopy(nums2, 0, a, nums1.length, nums2.length);
        Arrays.sort(a);
        if (a.length % 2 == 0) {
            int min = a.length / 2 - 1;
            int max = a.length / 2;
            System.out.println((double) (a[min] + a[max]) / 2);
            d = (double) (a[min] + a[max]) / 2;
        } else {
            int middle = a.length / 2;
            System.out.println(a[middle]);
            d = a[middle];
        }
        return d;
    }


    public String longestPalindrome(String s) {
        if (s == null || s.length() < 2) {
            return s;
        }
        char[] chars = s.toCharArray();
        char[] result = new char[s.length()];
        Map<Character, Integer> charsMap = new HashMap<>();
        int i = 0;
        int chongfuindex = -1;
        for (int j = i; j < chars.length; j++) {
            char c = chars[j];
            if (charsMap.containsKey(c)) {
                chongfuindex = charsMap.get(c);
            }
            charsMap.put(c, j);
        }
        return s;
    }


    /**
     * 兔子问题
     *
     * @param n
     * @return
     */
    public static int fib(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        //b：总的兔子对数
        //a: 增长的基数
        int a = 1, b = 1, temp;
        //i为月数，从第3个月开始递增
        for (int i = 3; i <= n; i++) {
            temp = b;
            b = a + b;
            a = temp;
        }
        return b;
    }


    /**
     * 字符串z字形变形
     *
     * @param s
     * @param numRows
     * @return
     */
    public static String convert(String s, int numRows) {
        /*
        if (numRows < 2 || s.length() <= numRows) {
            return s;
        }
        List<StringBuilder> rows = new ArrayList<>(numRows);
        for (int k = 0; k < numRows; k++) {
            rows.add(new StringBuilder());
        }
        int flag = -1;
        int i = 0;
        for (char c : s.toCharArray()) {
            if (i == 0 || i == rows.size() - 1) {
                flag = -flag;
            }
            rows.get(i).append(c);
            i += flag;
        }
        StringBuilder sb = new StringBuilder();
        for (StringBuilder row : rows) {
            sb.append(row);
        }
        return sb.toString();
        */


        //只有一个字符或者字符长度小于行数
        if (numRows < 2 || s.length() <= numRows) {
            return s;
        }
        char[] chars = s.toCharArray();
        //定义一个行数的数组，0~numRows-1 代表 1~numRows行
        String[] zc = new String[numRows];
        //当前字符对应行
        int num = 0;
        boolean down = true;
        for (int i = 0; i < chars.length; i++) {
            if (zc[num] == null) {
                zc[num] = "";
            }
            zc[num] += chars[i];
            if (down) {
                num++;
            } else {
                num--;
            }
            if (num == 0) {
                down = true;
            }
            if (num == numRows - 1) {
                down = false;
            }
        }
        String collect = Arrays.stream(zc).filter(Objects::nonNull).collect(Collectors.joining(""));
        return collect;
    }

    /**
     * 给你一个 31 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
     * <p>
     * 如果反转后整数超过 31 位的有符号整数的范围 [−231,  231 − 1] ，就返回 0。
     *
     * @param x
     * @return
     */
    public static int reverse(int x) {
        /**
        int reversed = 0;
        while (x != 0) {
            if (reversed <= Integer.MAX_VALUE / 10 && reversed >= Integer.MIN_VALUE / 10) {
                reversed = reversed * 10 + x % 10;
                x = x / 10;
            } else {
                return 0;
            }
        }
        return reversed;
        */

        //Math.pow(3,2)
//        if (x == 0 || x < -1 * Math.pow(2, 31) || x > Math.pow(2, 31) - 1) {
//            return 0;
//        }

        int result = 0;
        while (x != 0) {
            //取数：从右边弹出，取模运算
            //放数：推入到左边，乘10运算
            if (result <= Integer.MAX_VALUE / 10 && result >= Integer.MIN_VALUE / 10) {
                result = result * 10 + x % 10;
                x /= 10;
            } else {
                return 0;
            }
        }
        return result;
    }


    /**
     * 整数范围 [−231,  231 − 1] ，小于 −231 的整数应该被舍入为 −231 ，大于 231 − 1 的整数应该被舍入为 231 − 1
     *
     * @param s
     * @return
     */
    public static int myAtoi(String s) {
        return 0;
    }


    /**
     *给定链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
     *
     * PriorityQueue:基于优先级堆的无界优先级队列。优先级队列的元素根据其自然顺序排序，或者由队列构建时提供的Comparator排序，
     * 具体取决于使用的是哪个构造函数。优先级队列不允许null元素。依赖于自然排序的优先级队列也不允许插入不可比较的对象（这样做可能导致ClassCastException）。
     * @param head
     * @return
     */
    public static ListNode sortList(ListNode head) {
        PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>((a, b) -> a.val - b.val);
        while (head != null) {
            heap.offer(head);
            head = head.next;
        }
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        while (heap.size() > 0) {
            cur.next = heap.poll();
            cur = cur.next;
        }
        cur.next = null;
        return dummy.next;
    }


    public static ListNode sortList(ListNode head, ListNode tail) {
        if (head == null) {
            return head;
        }
        if (head.next == tail) {
            head.next = null;
            return head;
        }
        ListNode slow = head, fast = head;
        while (fast != tail) {
            slow = slow.next;
            fast = fast.next;
            if (fast != tail) {
                fast = fast.next;
            }
        }
        ListNode mid = slow;
        ListNode list1 = sortList(head, mid);
        ListNode list2 = sortList(mid, tail);
        ListNode sorted = merge(list1, list2);
        return sorted;
    }

    public static ListNode merge(ListNode head1, ListNode head2) {
        ListNode dummyHead = new ListNode(0);
        ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
        while (temp1 != null && temp2 != null) {
            if (temp1.val <= temp2.val) {
                temp.next = temp1;
                temp1 = temp1.next;
            } else {
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        if (temp1 != null) {
            temp.next = temp1;
        } else if (temp2 != null) {
            temp.next = temp2;
        }
        return dummyHead.next;
    }



    /**
     * 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配
     *
     * @param s
     * @param p
     * @return
     */
    public static boolean isMatch(String s, String p) {
        int sLen = s.length();
        int pLen = p.length();
        boolean[][] dp = new boolean[sLen + 1][pLen + 1];

        // 空字符串和空模式是匹配的
        dp[0][0] = true;

        // 处理模式中的 '*' 的情况
        for (int j = 1; j <= pLen; j++) {
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }

        // 填充动态规划表
        for (int i = 1; i <= sLen; i++) {
            for (int j = 1; j <= pLen; j++) {
                char sChar = s.charAt(i - 1);
                char pChar = p.charAt(j - 1);

                if (pChar == sChar || pChar == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (pChar == '*') {
                    dp[i][j] = dp[i][j - 2] || (matches(sChar, p.charAt(j - 2)) && dp[i - 1][j]);
                }
            }
        }

        return dp[sLen][pLen];
    }

    private static boolean matches(char sChar, char pChar) {
        return sChar == pChar || pChar == '.';
    }


    /**
     * 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配
     * @param s
     * @param p
     * @return
     */
//    private static boolean isMatch2(String s, String p) {
//
//    }


    /**
     * 7 8 9 10
     * 6 1 2 11
     * 5 4 3 12
     * - - - 13
     */
    public static void roundNums(int num) {
        double sqrt = Math.sqrt(num);
        //对平方根向上取整得到理想的方阵
        int pfg = (int) Math.ceil(sqrt);
        int[][] fz = new int[pfg][pfg];
        //得到开始点 1 的下标位置
        int index = pfg % 2 == 0 ? pfg / 2 - 1 : pfg / 2;
        //1的起始位置
        fz[index][index] = 1;
        //旋转的自增数字，自增到目标数字num，起始位置已经有了，所以从2开始
        int numincr = 2;
        //下左上右旋转,从2的位置开始
        boolean down = true, left = false, up = false, right = false;
        //初始化一个横向和纵向的初始坐标
        int hx = Integer.MIN_VALUE;
        int zx = Integer.MIN_VALUE;
        //定义一个最小的平方根递增到理想的平方根
        for (int minPfg = 2; minPfg <= pfg; minPfg++) {
            //回溯到上一个坐标点
            if (zx == Integer.MIN_VALUE && hx == Integer.MIN_VALUE) {
                //这里是从2的位置开始，向下走，所以假设一个横向和纵向的坐标点
                hx = index - 1;
                zx = index + 1;
            }
            //移动的步长
            int stepSize = 2 * minPfg - 1;
            int tmp = stepSize;
            //把平方根每增加1需要每增加数字个数看做循环的次数,2n-1
            for (int times = 2 * minPfg - 1; times > 0; times--) {
                if (numincr <= num) {
                    if (down) {
                        //向下走 横向坐标+1
                        hx++;
                        fz[hx][zx] = numincr;
                        numincr++;
                        //步长-1
                        tmp--;
                        if (stepSize - tmp == minPfg) {
                            down = false;
                            left = true;
                        }
                    } else if (left) {
                        //向左走 纵向坐标-1
                        zx--;
                        fz[hx][zx] = numincr;
                        numincr++;
                        //步长-1
                        tmp--;
                        if (tmp == 0) {
                            left = false;
                            up = true;
                            //开始旋转，假设上一个坐标点的位置，为下一个数建立参考点
                            hx++;
                            zx--;
                        }
                    } else if (up) {
                        //向上走 横向坐标-1
                        hx--;
                        fz[hx][zx] = numincr;
                        numincr++;
                        //步长-1
                        tmp--;
                        if (stepSize - tmp == minPfg) {
                            up = false;
                            right = true;
                        }
                    } else if (right) {
                        //向右走 总向坐标+1
                        zx++;
                        fz[hx][zx] = numincr;
                        numincr++;
                        //步长-1
                        tmp--;
                        if (tmp == 0) {
                            right = false;
                            down = true;
                            //开始旋转，假设上一个坐标点的位置，为下一个数建立参考点
                            hx--;
                            zx++;
                        }
                    }
                }
            }
        }
        for (int i = 0; i < fz.length; i++) {
            for (int i1 = 0; i1 < i; i1++) {
                System.out.print(i1 + "");
            }
            System.out.println();
        }
    }
}
